Approximating the minimum length of synchronizing words is hard

摘要

We prove that, unless $\mathrm{P}=\mathrm{NP}$, no polynomial algorithm canapproximate the minimum length of \sws for a given \san within a constantfactor.